package linked_list

import (
	"fmt"
	"go-demo/utils"
)

type Elem interface{}

// 定义节点
type SingleNode struct {
	Data Elem
	Next *SingleNode
}

// 单向链表
type SingleNodeList struct {
	headNode *SingleNode
}

// 判断是否为空的单链表
func (list *SingleNodeList) IsEmpty() bool {
	return utils.If(list.headNode == nil, true, false).(bool)
}

// 单链表的长度
func (list *SingleNodeList) Length() int {
	curNode := list.headNode
	len := 0

	for curNode != nil {
		len++
		curNode = curNode.Next
	}
	return len
}

//从头部添加元素
func (list *SingleNodeList) Add(data Elem) *SingleNode {
	node := &SingleNode{Data: data}
	if list.IsEmpty() {
		list.headNode = node
	} else {
		node.Next = list.headNode
		list.headNode = node
	}
	return node
}

//从尾部添加元素
func (list *SingleNodeList) Append(data Elem) {
	node := &SingleNode{Data: data}
	if list.IsEmpty() {
		list.headNode = node
	} else {
		curNode := list.headNode
		for curNode.Next != nil {
			curNode = curNode.Next
		}
		curNode.Next = node
	}
}

//在指定位置添加元素
func (list *SingleNodeList) Insert(index int, data Elem) {
	// 小于0,插入头部；大于链表长度,插入尾部
	if index < 0 {
		list.Add(data)
	} else if index > list.Length() {
		list.Append(data)
	} else {
		// 寻找index的前一个节点
		preNode := list.headNode
		count := 0
		for count < (index - 1) {
			preNode = preNode.Next
			count++
		}
		node := &SingleNode{Data: data}
		node.Next = preNode.Next
		preNode.Next = node
	}
}

//删除指定元素
func (list *SingleNodeList) Remove(data Elem) {
	preNode := list.headNode
	if preNode.Data == data {
		// 删除头节点
		list.headNode = preNode.Next
	} else {
		for preNode.Next != nil {
			if preNode.Next.Data == data {
				// 删除找到的节点
				preNode.Next = preNode.Next.Next
			} else {
				preNode = preNode.Next
			}
		}
	}
}

//删除指定位置的元素
func (list *SingleNodeList) RemoveAt(index int) {
	preNode := list.headNode
	// 小于0,删除头部；大于链表长度,报错
	if index <= 0 {
		list.headNode = preNode.Next
	} else if index > list.Length() {
		panic("index is out of range")
		return
	} else {
		count := 0
		// 找到需要查找的前一个节点
		for count != (index - 1) && preNode.Next != nil {
			count++
			preNode = preNode.Next
		}
		// 删除index节点
		preNode.Next = preNode.Next.Next
	}
}

//查看是否包含某个元素
func (list *SingleNodeList) Contain(data Elem) bool {
	preNode := list.headNode
	for preNode != nil {
		if preNode.Data == data {
			return true
		}
		preNode = preNode.Next
	}
	return false
}

//遍历所有元素
func (list *SingleNodeList) PrintList() {
	if !list.IsEmpty() {
		preNode := list.headNode
		for preNode != nil {
			fmt.Printf("\t%v",preNode.Data)
			preNode = preNode.Next
		}
		fmt.Println()
	}
}

// 获取链表中的第i个元素，复杂度为o(n)
func (list *SingleNodeList) Get(index int) Elem {
	preNode := list.headNode
	if index <= 0 {
		return preNode.Data
	} else if index >= list.Length() {
		panic("index is out of range")
	} else {
		count := 0
		// 找到需要查找的前一个节点
		for count != index && preNode.Next != nil {
			count++
			preNode = preNode.Next
		}
	}

	return preNode.Data
}
